package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.HashSet;
import java.util.Iterator;

/**
 * @author: ZhouBert
 * @date: 2021/3/16
 * @description: 718. 最长重复子数组
 * https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
 * 题解
 * https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/
 */
public class B_718_最长重复子数组 {

	static B_718_最长重复子数组 action = new B_718_最长重复子数组();

	public static void main(String[] args) {
		test1();
		test2();
	}

	public static void test1() {
		//3
		int[] A = new int[]{1, 2, 3, 2, 1};
		int[] B = new int[]{3, 2, 1, 4, 7};
		int lists = action.findLengthByIndex(A, B);
		System.out.println("lists = " + lists);
	}

	public static void test2() {
		//2
		int[] A = new int[]{0, 1, 1, 1, 1};
		int[] B = new int[]{1, 0, 1, 0, 1};
		int lists = action.findLengthByIndex(A, B);
		System.out.println("lists = " + lists);
	}


	/**
	 * 如果不用 dp 来解的话，由于长度才 1000，应该不会超时。
	 * 战绩：2225 ms, 在所有 Java 提交中击败了5.14% 的用户
	 * --
	 * 是否可以基于暴力解法进行优化呢？
	 * 首先看看有木有重复计算的部分
	 * 我的发现：
	 * 对于 A 中的元素，寻找 B 中与 该元素相等的位置，该部分存在重复计算；
	 *
	 * @param A
	 * @param B
	 * @return
	 */
	public int findLengthByForce(int[] A, int[] B) {
		int lenA = A.length;
		int lenB = B.length;
		int res = 0;
		for (int i = 0; i < lenA; i++) {
			for (int j = 0; j < lenB; j++) {
				if (A[i] == B[j]) {
					//继续比较
					int it = i + 1;
					int jt = j + 1;
					while (it < lenA && jt < lenB) {
						if (A[it] != B[jt]) {
							//如果不相等
							break;
						}
						it++;
						jt++;
					}
					res = Math.max(res, it - i);
				}
			}
		}
		return res;
	}

	/**
	 * 通过 DP 优化上述的 force
	 * 由于 0 <= A[i], B[i] < 100
	 * 那么可以用数组进行记录；
	 * 另一方面：dp[i] 表示 A 中 i 处结果的重复子数组的最大长度，但是 dp[i] 的结果是与 dp[i-1] 从何种方式得来是有关系的！
	 * 所以，其实不能在这里用 DP !
	 * 如果这么设计了，感觉就比较难写了。
	 * --
	 * 真正好的思路不该这么难写的
	 * 这个最坏时间复杂度也是 n^2 卧槽几乎没有优化！
	 * @param A
	 * @param B
	 * @return
	 */
	public int findLengthByIndex(int[] A, int[] B) {
		int lenA = A.length;
		int lenB = B.length;
		int res = 0;
		//相当于借助了一个索引的结构
		HashSet<Integer>[] recorder = new HashSet[100];
		for (int i = 0; i < lenB; i++) {
			if (recorder[B[i]] == null) {
				HashSet<Integer> set = new HashSet<>();
				set.add(i);
				recorder[B[i]] = set;
			} else {
				recorder[B[i]].add(i);
			}
		}
		//遍历 A，对 B中匹配该元素的位置全部进行遍历
		for (int i = 0; i < lenA; i++) {
			if (recorder[A[i]] != null) {
				//如果
				HashSet<Integer> tempSet = (HashSet<Integer>) recorder[A[i]].clone();
				int j = i + 1;
				while (!tempSet.isEmpty()) {
					Iterator<Integer> iterator = tempSet.iterator();
					while (iterator.hasNext()) {
						Integer item = iterator.next();
						if (item + j - i == lenA || j == lenA) {
							//越界
							iterator.remove();
							continue;
						}
						//这里有个 BUG 而且思路有点绕，不好搞清楚！
						if (recorder[A[j]] != null && recorder[A[j]].contains(item + j - i)) {
							//合格

						} else {
							iterator.remove();
						}
					}
					j++;

				}
				res = Math.max(res, j - i - 1);
			}
		}
		return res;
	}


}
